题目
给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
1 2
| 输入: rowIndex = 3 输出: [1,3,3,1]
|
示例 2:
1 2
| 输入: rowIndex = 0 输出: [1]
|
示例 3:
1 2
| 输入: rowIndex = 1 输出: [1,1]
|
提示:
注意要点
没啥注意的,考察数组知识。这里记录一些可以节约时间、空间的奇淫巧技
最普通做法 二维数组
二维数组,模拟铺开
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public: vector<int> getRow(int rowIndex) { vector<vector<int>> yanghui(rowIndex+1); for(int i=0;i<=rowIndex;i++){ yanghui[i].resize(i+1); yanghui[i][0]=yanghui[i][i]=1; for(int j=1;j<i;j++){ yanghui[i][j] = yanghui[i-1][j-1]+yanghui[i-1][j]; } } return yanghui[rowIndex]; } };
|
两个一维数组
二维数组我们可以发现,当前层只跟上一层有关系,那么只记录上一层就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public: vector<int> getRow(int rowIndex) { vector<int> pre,cur;
for(int i=0;i<=rowIndex;i++){ cur.resize(i+1); cur[0]=cur[i]=1; for(int j=1;j<i;j++){ cur[j] = pre[j-1]+pre[j]; } pre = cur; } return cur; } };
|
一个一维数组
我们还发现当前层的数只和上一层的该位置的数和前一个位置数有关,那么我们可以不破坏前一个数,倒着更新当前数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public: vector<int> getRow(int rowIndex) { vector<int> cur(rowIndex+1); cur[0]=1; for(int i=1;i<=rowIndex;i++){ for(int j=i;j>0;j--){ cur[j] = cur[j]+cur[j-1]; } } return cur; } };
|
原文链接: https://zijian.wang/2021/09/14/119. 杨辉三角II(数学)/
版权声明: 转载请注明出处.